package org.example.day02;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * 有一个考古学家发现一个石碑，但是很可惜，发现时其已经断成多段，原地发现n个断口整齐的石碑碎片。为了破解石碑内容，考古学家希望有程序能帮忙计算复原后的石碑文字组合数，你能帮忙吗？<span></span>
 * @date 2024/3/11 15:22
 */
public class test035 {
    public static void main(String[] args) {
        // 读取输入的石碑碎片个数和碎片内容
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String[] fragments = new String[n];
        for (int i = 0; i < n; i++) {
            fragments[i] = scanner.next();
        }

        // 使用Arrays类的sort方法对碎片内容进行排序
        Arrays.sort(fragments);

        // 使用递归函数生成所有可能的排列组合，并进行去重
        Set<String> combinations = new HashSet<>();
        generateCombinations(fragments, new boolean[n], new StringBuilder(), combinations);

        // 对结果进行排序
        List<String> sortedCombinations = new ArrayList<>(combinations);
        Collections.sort(sortedCombinations);

        // 输出排列组合
        for (String combination : sortedCombinations) {
            System.out.println(combination);
        }
    }

    // 递归生成所有可能的排列组合
    private static void generateCombinations(String[] fragments, boolean[] used, StringBuilder currentCombination, Set<String> combinations) {
        // 如果当前排列组合长度等于石碑碎片个数，表示已经生成了一种排列组合
        if (currentCombination.length() == fragments.length) {
            combinations.add(currentCombination.toString()); // 将排列组合加入结果集合
            return;
        }

        // 依次尝试将每个碎片放入排列组合中
        for (int i = 0; i < fragments.length; i++) {
            if (!used[i]) { // 如果当前碎片未被使用过
                used[i] = true; // 将碎片标记为已使用
                currentCombination.append(fragments[i]); // 将碎片加入排列组合
                generateCombinations(fragments, used, currentCombination, combinations); // 递归生成下一个位置的排列组合
                currentCombination.deleteCharAt(currentCombination.length() - 1); // 回溯，将当前位置的碎片移出排列组合
                used[i] = false; // 将碎片标记为未使用
            }
        }
    }
}

